package com.myutil.graph;

import java.util.ArrayList;

public class Graph {
	
	//邻接边，储存边的长度，有向图
	private double[][] adjEdges;
	//邻接节点，储存点的编号
	private int[][] adjNodes;
	
	private int start;
	private int destination;
	public int maxLimit=0x7fffffff;

	public Graph(double[][] adjEdges,int[][] adjNodes) {
		this.adjEdges=adjEdges;
		this.adjNodes=adjNodes;
	}
	
	public void setDefaultParam(int maxLimit){
		this.maxLimit=maxLimit;
	}
	
	public void setPoints(int start, int destination){
		this.start=start;
		this.destination=destination;
	}
	
	public ArrayList<Integer> findMixRoute(){
		double[] sourceCost=new double[this.adjNodes.length];
		int[] path=new int[sourceCost.length];//前驱
		
		for(int i=0;i<sourceCost.length;i++){
			sourceCost[i]=this.maxLimit;
			path[i]=i;
		}
		sourceCost[start]=0;
		for(int i=0;i<this.adjNodes[start].length;i++){
			sourceCost[this.adjNodes[start][i]]=this.adjEdges[start][i];
			path[this.adjNodes[start][i]]=start;
		}
		
		//spfa
		IntQueue queue=new IntQueue();
		for(int node:adjNodes[start]){
			queue.add(node);
		}
		while(queue.length>0){
			int temp=queue.remove();
			for(int i=0;i<adjNodes[temp].length;i++){
				if(sourceCost[temp]+adjEdges[temp][i]<sourceCost[adjNodes[temp][i]]){
					sourceCost[adjNodes[temp][i]]=sourceCost[temp]+adjEdges[temp][i];
					path[adjNodes[temp][i]]=temp;
					queue.add(adjNodes[temp][i]);
				}
			}
		}
		queue.destroy();
		
		//返回结果
		int dest=destination;
		ArrayList<Integer> ls=new ArrayList<>();
		while(dest!=start){
			ls.add(dest);
			dest=path[dest];
		}
		ls.add(start);
		return ls;
	}

}
